package com;

public class zuoye<ListGraphNode> {

    public class Dijkstra2<Integer, Hashtable> {

        //图的顶点数组
        private ListGraphNode []nodes;

        private Hashtable valueindex=new Hashtable<Integer,Integer>();

        //初始化图的顶点
        public Dijkstra2(int []vetexes)
        {
            nodes=new ListGraphNode[vetexes.length];

            for(int i=0;i<vetexes.length;i++)
            {

                //初始化每个节点
                nodes[i]=new ListGraphNode(i,vetexes[i],null);
                //hash记录每个位置
                valueindex.put(vetexes[i], i);
            }
        }

        public void addEdge(int start ,int []end,int[]weights)
        {

            int index=valueindex.get(start);
            if(index<0)
            {
                throw new RuntimeException("未找到指定的起始顶点!");
            }
            ListGraphNode node=nodes[index];

            for(int j=0;j<end.length;j++)
            {
                int k=valueindex.get(end[j]);

                if(k<0)
                {
                    throw new RuntimeException("未找到指定的到达顶点!");
                }
                node.next=new ListGraphNode(k,end[j],weights[j],null);
                node=node.next; //链接下一个

            }
        }

        //Dijkstra算法实现到各点的最短路径


        public void dijkstra(int start) {
            int length = nodes.length;
            int x = valueindex.get(start);   //记录起始点
            if (x == -1) {
                throw new RuntimeException("未找到起始顶点");
            }

            //自动初始化为0，都属于未得到最短路径的顶点
            int[] s = new int[length];
            //存储v到u的最短距离
            int[][] distance = new int[length][length];
            //存储x到u最短路径时u的前一个顶点
            int[] path = new int[length];

            //初始化path数组
            for (int i = 0; i < length; i++) {

                //初始化path为-1
                path[i] = -1;
            }
            for (int i = 0; i < length; i++) {
                ListGraphNode node = nodes[i];
                node = node.next;
                while (node != null) {
                    distance[i][node.index] = node.weight;

                    if (x == i) {
                        //如果是x顶点的链表，则初始化所有可达顶点的前一个顶点为x
                        path[node.index] = x;
                    }
                    node = node.next;
                }

            }

            //先把起始顶点加入s
            s[x] = 1;

            for (int i = 0; i < length; i++) {
                //首先需要寻找start顶点到各顶点最短的路径
                int min = Integer.MAX_VALUE;
                int v = 0;  //记录x到各顶点最短的
                for (int j = 0; j < length; j++) {     //s[j]==1说明已经找到最短路径
                    if (s[j] != 1 && x != j && distance[x][j] != 0 && distance[x][j] < min) {
                        min = distance[x][j];
                        v = j;
                    }
                }

                for (int j = 0; j < length; j++) {
                    if (s[j] != 1 && distance[v][j] != 0 && (min + distance[v][j] < distance[x][j] || distance[x][j] == 0)) {
                        //说明加入了中间顶点之后找到了更短的路径
                        distance[x][j] = min + distance[v][j];
                        path[j] = v;

                    }
                }

            }

        }
    }
}